Let $g(n)$ be the least number such that every collection of $n$ matchings,each of size at least $g(n)$, in a bipartite graph, has a full rainbowmatching. Aharoni and Berger \cite{AhBer} conjectured that $g(n)=n+1$ for every$n>1$. This generalizes famous conjectures of Ryser, Brualdi and Stein.Recently, Aharoni, Charbit and Howard \cite{ACH} proved that$g(n)\le\lfloor\frac{7}{4}n\rfloor$. We prove that $g(n)\le\lfloor\frac{5}{3}n\rfloor$.
展开▼
机译：令$ g（n）$为最小数，以使二元图中每个$ n $匹配集合的大小至少为$ g（n）$都具有完整的Rainbowmatching。 Aharoni和Berger \ cite {AhBer}推测每$ n> 1 $，$ g（n）= n + 1 $。这概括了Ryser，Brualdi和Stein的著名猜想。最近，Aharoni，Charbit和Howard \ cite {ACH}证明了$ g（n）\ le \ lfloor \ frac {7} {4} n \ rfloor $。我们证明$ g（n）\ le \ lfloor \ frac {5} {3} n \ rfloor $。
展开▼
